package com.yiwenup.leetcode.daily;

import java.util.ArrayList;
import java.util.List;

/**
 * 文件描述
 *
 * @Project struct-algorithm
 * @Package com.yiwenup.leetcode.daily
 * @Author yiwenup
 * @Date 2022-04-18 20:32:45
 * @Description https://leetcode-cn.com/problems/lexicographical-numbers/
 */
public class No0386 {

    /**
     * 执行用时：5 ms, 在所有 Java 提交中击败了17.42%的用户
     * 内存消耗：44.5 MB, 在所有 Java 提交中击败了87.77%的用户
     */
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>(n);

        int num = 1;
        for (int i = 1; i <= n; i++) {
            res.add(num);
            if (num * 10 <= n) {
                num *= 10;
            } else {
                while (num % 10 == 9 || num + 1 > n) {
                    num /= 10;
                }
                num++;
            }
        }

        return res;
    }
}
